package 二分查找;

import java.util.Arrays;

public class TwoFen {
    public static void main(String[] args) {
        int[] array = {12, 23, 56, 53, 32, 76, 57};


        int target=56;

        int i = binarySearch(array, target);
        System.out.println(i);
        int i1 = left_bound(array, target);
        System.out.println(i1);
        int i2 = right_bound(array, target);
        System.out.println(i2);

    }
//基本的二分搜索
    static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1; // 注意
        while (left <= right) { // 注意
            int mid = (right + left)/2;
            if (array[mid] == target)
                return mid;
            else if (array[mid] < target)
                left = mid + 1; // 注意
            else if (array[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }
//寻找左侧边界的二分搜索
    static int left_bound(int[] array, int target) {
        if (array.length == 0) return -1;
        int left = 0;
        int right = array.length; // 注意

        while (left < right) { // 注意
            int mid = (left + right) / 2;
            if (array[mid] == target) {
                right = mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid; // 注意
            }
        }
        return left;
    }
//寻找右侧边界的二分搜索
    static int right_bound(int[] array, int target) {
        if (array.length == 0) return -1;
        int left = 0, right = array.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (array[mid] == target) {
                left = mid + 1; // 注意
            } else if (array[mid] < target) {
                left = mid + 1;
            } else if (array[mid] > target) {
                right = mid;
            }
        }
        return left - 1; // 注意
    }
}